package domd8;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    //创建二插数
   public static int i=0;
    public static TreeNode createTree(String str){
        TreeNode  root=null;
        if(str.charAt(i)!='#'){
         root=new TreeNode(str.charAt(i));

         i++;
         root.left= createTree(str);
         root.right= createTree(str);
        }else {
            i++;
        }
        return root;
    }
    //中序遍历
    public static void ordermid(TreeNode root){
     if(root==null){
           return ;
       }
     ordermid(root.left);
     //打印
        System.out.print(root.val+" ");
     ordermid(root.right);
    }
    //层次遍历
    public void leveTree(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
      while (!queue.isEmpty()){
          TreeNode cur=queue.poll();
          System.out.print(cur.val+" ");
          if(cur.left!=null){
              queue.offer(cur.left);
          }
          if(cur.right!=null){
              queue.offer(cur.right);
          }
      }
    }
    public List<List<Character>> LeveTree(TreeNode root) {
        List<List<Character>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Character> list = new LinkedList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
               size--;
            }
            ret.add(list);
        }
        System.out.println();
        return ret;
    }
    //判断是否是完全二插数
    public boolean CompleteTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if (cur!= null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode peek=queue.peek();
            if(peek!=null){
                return false;
            }else {
                queue.poll();
            }
        }
        return true;
    }
    //判断二叉数的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else {
            return rightTree;
        }
    }
}
